package main

import (
	"fmt"
)

/**
双向链表节点
*/
type DoubleNode struct {
	no   int         //编号
	data interface{} //数据域
	prev *DoubleNode //prev指针域，指向前一个节点
	next *DoubleNode //next指针域，指向后一个节点
}

/**
在双向链表的末尾添加新节点
*/
func Add(head *DoubleNode, node *DoubleNode) {
	temp := head
	for true {
		if temp.next != nil {
			temp = temp.next
		} else {
			//修改temp的next域指针指向新添加的节点
			temp.next = node
			//修改新添加的节点的prev指针指向temp节点
			node.prev = temp
			break
		}
	}
}

/**
根据编号顺序插入新节点
*/
func AddDoubleNodeByNo(head *DoubleNode, node *DoubleNode) {
	temp := head
	for true {
		if temp.next != nil {
			if temp.next.no >= node.no {
				//修改新加的节点的next指向
				node.next = temp.next
				//修改temp.next的前置指针
				temp.next.prev = node

				temp.next = node
				node.prev = temp

				break
			} else {
				temp = temp.next
			}
		} else {
			temp.next = node
			node.prev = temp
			//直接在temp的末尾添加
			break
		}
	}
}

/**
根据编号删除指定的节点
*/
func DelteDoubleNodeByNo(head *DoubleNode, no int) {
	temp := head
	for true {
		if temp.next != nil {
			if temp.next.no == no {

				//temp.next 是需要删除的节点

				//temp.next的后一个节点就是 temp.next.next
				//先修改指向前驱
				if temp.next.next != nil {
					temp.next.next.prev = temp
					temp.next = temp.next.next
				} else {
					//这种情况是链表中删到最后一个节点了，
					temp.next = nil
				}
				break
			} else {
				//继续往后寻找
				temp = temp.next
			}
		} else {
			//找完整个双向链表都没找到要删除的节点编号
			break
		}
	}
}

/**
初始化双向链表的节点
*/
func NewDoubleNode(value interface{}, no int) *DoubleNode {
	node := new(DoubleNode)
	node.data = value
	node.no = no
	return node
}

/**
顺序显示双向链表
*/
func ShowDoubleList(head *DoubleNode) {
	temp := head
	if temp.next == nil {
		fmt.Println("当前双向链表为空!")
		return
	}

	for true {
		fmt.Printf("节点_data:%v,no:%d\n", temp.data, temp.no)
		if temp.next != nil {
			temp = temp.next
		} else {
			break
		}
	}
}

/**
逆序显示双向链表
*/
func ReverseDoubleList(head *DoubleNode) {
	temp := head
	if temp.next == nil {
		fmt.Println("当前双向链表为空!")
		return
	}
	for true {
		if temp.next != nil {
			temp = temp.next
		} else {
			//找到最后那个节点
			for true {
				fmt.Printf("节点_data:%v,no:%d\n", temp.data, temp.no)
				if temp.prev != nil {
					temp = temp.prev
				} else {
					break
				}
			}
			break
		}
	}
}

/**
双向链表
*/
func main() {
	head := new(DoubleNode)
	n3 := NewDoubleNode("3号", 3)
	AddDoubleNodeByNo(head, n3)

	n1 := NewDoubleNode("1号", 1)
	AddDoubleNodeByNo(head, n1)
	n2 := NewDoubleNode("2号", 2)
	AddDoubleNodeByNo(head, n2)

	//ShowDoubleList(head)
	fmt.Println("未删除前，逆序输出：")
	ReverseDoubleList(head)

	DelteDoubleNodeByNo(head, 2)
	DelteDoubleNodeByNo(head, 1)
	DelteDoubleNodeByNo(head, 3)

	fmt.Println("删除后，再次逆序输出:")
	ReverseDoubleList(head)
}
